package cn.zhl.algorithm._2_动态规划;

/**
 * @program: demos
 * @description: 有25，20，5，1四种硬币，求凑得41分硬币的最少个数
 * @author: 刘振华
 * @create: 2020-09-11 10:42
 **/
public class CoinNums {
	public static void main(String[] args) {
		int[] coins = {2,5,20,25};
//		System.out.println(get2Init(41,coins));
		System.out.println(get6WithCoin(42,coins));
	}

	static int get6WithCoin(int n,int[] coins) {
		int min = coins[0];
		if (n < min) {
			return -1;
		}
		int[] rs = new int[n + 1];
		rs[min] = 1;
		for (int i = min + 1; i <= n; i++) {
			int tmin = rs[i - 1];
			for(int j = 1;j<coins.length;j++){
				if (i >= coins[j]) {
					tmin = Math.min(tmin, rs[i - coins[j]]);
				}
			}
			rs[i] = tmin + 1;
		}
		return rs[n];
	}

	static int get5WithCoin(int n,int[] coins){
		int min = coins[0];
		if(n < min) {
			return -1;
		}
		int[] rs = new int[n + 1];
		rs[min] = 1;
		int[] coinRs = new int[n+1];
		coinRs[min] = min;
		for(int i = min+1;i<=n;i++){
			int a = min;
			int tmin = rs[i - 1];
			int rsMin = tmin;
			if (i  >= 5) {
				tmin = Math.min(tmin, rs[i - 5]);
				if(rsMin != tmin){
					a = 5;
					rsMin = tmin;
				}
			}
			if (i >= 20) {
				tmin = Math.min(tmin, rs[i - 20]);
				if(rsMin != tmin){
					a = 20;
					rsMin = tmin;
				}
			}
			if (i >= 25) {
				tmin = Math.min(tmin, rs[i - 25]);
				if(rsMin != tmin){
					a = 25;
					rsMin = tmin;
				}
			}
			rs[i] = tmin + 1;
			coinRs[i] = a;
//			System.out.print(rs[i]+"\t");
		}
//		System.out.println();
		for(int i = n;i>0;){
			int step = coinRs[i];
			System.out.print(step+"\t");
			i -= step;
		}
		System.out.println();
		return rs[n];
	}
	static int get4WithCoin(int n,int[] coins){
		int min = coins[0];
		if(n < min) {
			return -1;
		}
		int[] rs = new int[n + 1];
		rs[min] = 1;
		for(int i = min+1;i<=n;i++){
			int tmin = rs[i - 1];
			if (i  >= 5) {
				tmin = Math.min(tmin, rs[i - 5]);
			}
			if (i >= 20) {
				tmin = Math.min(tmin, rs[i - 20]);
			}
			if (i >= 25) {
				tmin = Math.min(tmin, rs[i - 25]);
			}
			rs[i] = tmin + 1;
//			System.out.print(rs[i]+"\t");
		}
//		System.out.println();
		return rs[n];
	}
	static int get3WithCoin(int n,int[] coins){
		int min = coins[0];
		if(n < min) {
			return -1;
		}
		int[] rs = new int[n + 1];
		for(int i = 0;i<coins.length;i++){
			int idx = coins[i];
			if(idx <= n) {
				rs[idx] = 1;
			}else {
				break;
			}
		}
		for(int i = min+1;i<=n;i++){
			if(rs[i]==0) {
				int tmin = rs[i - 1];
				if (i - 5 >= min) {
					tmin = Math.min(tmin, rs[i - 5]);
				}
				if (i - 20 >= min) {
					tmin = Math.min(tmin, rs[i - 20]);
				}
				if (i - 25 >= min) {
					tmin = Math.min(tmin, rs[i - 25]);
				}
				rs[i] = tmin + 1;
			}
		}
		return rs[n];
	}

	/**
	 * @Description: 记忆递归，自上而下
	 * @return:
	 * @Author: 刘振华
	 * @Date: 2020/9/11 12:55
	 */
	static int get2Init(int n,int[] coins){
		if(n < 1) {
			return -1;
		}
		int[] rs = new int[n + 1];
		for(int i = 0;i<coins.length;i++){
			int idx = coins[i];
			if(idx <= n) {
				rs[idx] = 1;
			}else {
				break;
			}
		}
		return get2(n,rs);
	}
	static int get2(int n,int[] rs){
		if(n<1){
			return Integer.MAX_VALUE;
		}
		if(rs[n] == 0){
			//说明是第一次进入这里，如果是后续进入的话，那么就直接返回了
			int min1 = Math.min(get2(n-1,rs),get2(n-5,rs));
			int min2 = Math.min(get2(n-20,rs),get2(n-25,rs));
			rs[n] = Math.min(min1,min2) + 1;
		}
		return rs[n];
	}
	/**
	 * @Description: 暴利递归
	 * @return:
	 * @Author: 刘振华
	 * @Date: 2020/9/11 12:55
	 */
	static int get1(int n){
		if(n<1) {
			return Integer.MAX_VALUE;
		}
		if(n == 1 || n ==5 || n == 20 || n == 25){
			return 1;
		}

		int min1 = Math.min(get1(n-1),get1(n-5));
		int min2 = Math.min(get1(n-20),get1(n-25));
		return Math.min(min1,min2) + 1;

	}
}
